import collections
class Solution(object):
    def validArrangement(self, pairs):
        du = collections.defaultdict(int)
        d = collections.defaultdict(set)
        for u, v in pairs:
            du[u] += 1
            du[v] -= 1
            d[u].add(v)
        start = pairs[0][0]
        for key in du:
            if du[key] == 1:
                start = key
                break
        ans = []
        def dfs(node):
            while d[node]:
                v = d[node].pop()
                dfs(v)
            ans.append(node)
        dfs(start)
        ans.reverse()
        out = []
        for i in range(len(ans) - 1):
            out.append([ans[i], ans[i + 1]])
        return out

data = Solution()
pairs = [[5,1],[4,5],[11,9],[9,4]]
print(data.validArrangement(pairs))